// 16.2 模板实参推断
/**
 * 对于函数模板，编译器利用调用中的函数实参来确定其模板参数。从函数实参来确定模板实参的过程被称为模板实参推断（template argument deduction）。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <memory>
#include <new>
using namespace std;
#include <functional>
#include "../VisualStudio2012/15/Quote.h"
#include "../VisualStudio2012/12/TextQuery.h"

int main()
{
    // 16.2.1 类型转换与模板类型参数
    // 如果一个函数形参的类型使用了模板类型参数，那么它采用特殊的初始化规则。只有很有限的几种类型转换会自动地应用于这些实参。编译器通常不是对实参进行类型转换，而是生成一个新的模板实例。
    // 与往常一样，顶层const（参见2.4.3节，第57页）无论是在形参中还是在实参中，都会被忽略。
    // 能在调用中应用于函数模板的包括如下两项。
    //   · const转换：可以将一个非const对象的引用（或指针）传递给一个const的引用（或指针）形参（参见4.11.2节，第144页）。
    //   · 数组或函数指针转换：如果函数形参不是引用类型，则可以对数组或函数类型的实参应用正常的指针转换。一个数组实参可以转换为一个指向其首元素的指针。
    //     类似的，一个函数实参可以转换为一个该函数类型的指针（参见4.11.2节，第143页）。
    // 其他类型转换，如算术转换（参见4.11.1节，第142页）、派生类向基类的转换（参见15.2.2节，第530页）以及用户定义的转换（参见7.5.4节，第263页和14.9节，第514页），都不能应用于函数模板。
    /*
template<typename T> T fobj(T,T); // 实参被拷贝
template<typename T> T fref(const T&,const T&); // 引用
string s1("a value");
const string s2("another val");
fobj(s1,s2); // 调用fobj(string,string)；const被忽略
fref(s1,s2); // 调用fref(const string&,const string&)；将s1转换为const是允许的
int a[10],b[42];
fobj(a,b); // 调用fobj(int*,int*)
fref(a,b); // 错误，数组类型不匹配
在下一对调用中，我们传递了数组实参，两个数组大小不同，因此是不同类型。在fobj调用中，数组大小不同无关紧要。两个数组都被转换为指针。fobj中的模板类型为int＊。
但是，fref调用是不合法的。如果形参是一个引用，则数组不会转换为指针（参见6.2.4节，第195页）。a和b的类型是不匹配的，因此调用是错误的。
    */
    // 将实参传递给带模板类型的函数形参时，能够自动应用的类型转换只有const转换及数组或函数到指针的转换。

    // 使用相同模板参数类型的函数形参
    // 一个模板类型参数可以用作多个函数形参的类型。由于只允许有限的几种类型转换，因此传递给这些形参的实参必须具有相同的类型。如果推断出的类型不匹配，则调用就是错误的。
/*
例如：
long lng;
// compare函数（参见16.1.1节，第578页）接受两个const T&参数
compare(lng,1024); // 错误：lng的类型是long，而1024的类型是int，不能实例化compare(long, int);
// 如果希望允许对函数实参进行正常的类型转换，我们可以将函数模板定义为两个类型参数：
// 实参类型不同，但必须兼容
template<typename A, typename B>
int flexibleCompare(cosnt A& v1, const B& v2)
{
    if(v1<v2) return -1;
    if(v1>v2) return 1;
    return 0;
}
// 现在用户可以提供不同类型的实参了
long lng;
flexibleCompare(lng, 1024); // 正确，调用flexibleCompare(long, int)
*/
    
    // 正常类型转换应用于普通函数实参
    // 函数模板可以有用普通类型定义的参数，即，不涉及模板类型参数的类型。这种函数实参不进行特殊处理；它们正常转换为对应形参的类型（参见6.1节，第183页）。
    /*
例如：
template<typename T> ostream &print(ostream &os, const T &obj)
{
    return os << obj;
}
第一个函数参数是一个已知类型ostream&。第二个参数obj则是模板参数类型。由于os的类型是固定的，因此当调用print时，传递给它的实参会进行正常的类型转换：
print(cout, 42); // 实例化print(ostream&, int);
ofstream f("output");
print(f, 10); // 使用print(ostream&, int)；将f转换为ostream&
    */
    // 如果函数参数类型不是模板参数，则对实参进行正常的类型转换

    // 16.2.2 函数模板显式实参
    // 在某些情况下，编译器无法推断出模板实参的类型。其他一些情况下，我们希望允许用户控制模板实例化。当函数返回类型与参数列表中任何类型都不相同时，这两种情况最常出现。

    // 指定显式模板实参
    // 作为一个允许用户指定使用类型的例子，我们将定义一个名为sum的函数模板，它接受两个不同类型的参数。我们希望允许用户指定结果的类型。这样，用户就可以选择合适的精度。
    /*
template<typename T1, typename T2, typename T3>
T1 sum(T2 a, T3 b);
我们提供显式模板实参的方式与定义类模板实例的方式相同。显式模板实参在尖括号中给出，位于函数名之后，实参列表之前：
// T1是显示指定的，T2和T3是从函数实参类型推断而来的
auto val3 = sum<long long>(i, lng); // long long sum(int, long)
此调用显示指定T1类型，而T2、T3的类型由编译器从i和lng的类型推断而来
显式模板实参按由左至右的顺序与对应的模板参数匹配；第一个模板实参与第一个模板参数匹配，第二个实参与第二个参数匹配，依此类推。
  只有尾部（最右）参数的显式模板实参才可以忽略，而且前提是它们可以从函数参数推断出来。
// 糟糕的设计：用户必须指定三个模板参数
template<typename T1, typename T2, typename T3>
T3 alternative_sum(T2, T1);
// 错误：不能推断前几个模板参数
auto val3 = alternative_sum<long long>(i, lng);
// 证书：显示指定了所有三个参数
auto val2 = alternative_sum<long long, int, long>(i, lng);
    */

    // 正常类型转换应用于显式指定的实参
    // 对于用普通类型定义的函数参数，允许进行正常的类型转换（参见16.2.1节，第602页），出于同样的原因，对于模板类型参数已经显式指定了的函数实参，也进行正常的类型转换：
    /*
long lng;
compare(lng, 1024);       // 错误，模板参数不匹配
compare<long>(lng, 1024); // 正确，实例化compare(long,long)
compare<int>(lng, 1024);  // 正确，实例化compare(int,int)
    */

    // 16.2.3 尾置返回类型与类型转换
    // 当我们希望用户确定返回类型时，用显式模板实参表示模板函数的返回类型是很有效的。但在其他情况下，要求显式指定模板实参会给用户增添额外负担，而且不会带来什么好处。
    // 例如，我们可能希望编写一个函数，接受表示序列的一对迭代器和返回序列中一个元素的引用：
    /*
template<typename It>
??? &fcn(It beg, It end)
{
    // 处理序列
    return *beg;
}
我们并不知道返回结果的准确类型，但知道所需类型是所处理的序列的元素类型：
vector<int> vi = { 1,2,3,4,5 };
Blob<string> ca = { "hi", "bye" };
auto &i = fcn(vi.begin(), vi.end()); // fcn应该返回int&
auto &s = fcn(ca.begin(), ca.end()); // fcn应该返回string&
此例中，我们知道函数应该返回＊beg，而且知道我们可以用decltype（＊beg）来获取此表达式的类型。但是，在编译器遇到函数的参数列表之前，beg都是不存在的。
为了定义此函数，我们必须使用尾置返回类型（参见6.3.3节，第206页）。
// 尾置返回允许我们在参数列表之后声明返回类型
template<typename It>
auto fcn(It beg, It end) -> decltype(*beg)
{
    // 处理序列
    return *beg; // 返回序列中一个元素的引用
}
解引用运算符返回一个左值（参见4.1.1节，第121页），因此通过decltype推断的类型为beg表示的元素的类型的引用。
内置解引用运算符、下标运算符（参见2.3.2节，第48页；参见3.5.2节，第104页）、迭代器解引用运算符、
  string和vector的下标运算符（参见3.4.1节，第95页；参见3.2.3节，第83页；参见3.3.3节，第91页）的求值结果都是左值。
使用关键字decltype（参见2.5.3节，第62页）的时候，左值和右值也有所不同。如果表达式的求值结果是左值，decltype作用于该表达式（不是变量）得到一个引用类型。
  举个例子，假定p的类型是int＊，因为解引用运算符生成左值，所以decltype（＊p）的结果是int&。另一方面，因为取地址运算符生成右值，所以decltype（&p）的结果是int＊＊，
  也就是说，结果是一个指向整型指针的指针。
    */
    vector<int> vi = {1, 2, 3, 4, 5};
    vector<int>::iterator beg =  vi.begin();
    int a = 1;
    decltype(*beg) x = a; // x是int&类型，即引用类型
    int b = *beg;

    // 进行类型转换的标准库模板类
    // 有时我们无法直接获得所需要的类型。例如，我们可能希望编写一个类似fcn的函数，但返回一个元素的值（参见6.3.2节，第201页）而非引用。
    /*
为了获得元素类型，我们可以使用标准库的类型转换（type transformation）模板。这些模板定义在头文件type_traits中。这个头文件中的类通常用于所谓的模板元程序设计，这一主题已超出本书的范围。
  但是，类型转换模板在普通编程中也很有用。表16.1列出了这些模板，我们将在16.5节（第624页）中看到它们是如何实现的。在本例中，我们可以使用remove_reference来获得元素类型。
  remove_reference模板有一个模板类型参数和一个名为type的（public）类型成员。如果我们用一个引用类型实例化remove_reference，则type将表示被引用的类型。
组合使用remove_reference、尾置返回及decltype，我们就可以在函数中返回元素值的拷贝：
template<typename It>
auto fcn2(It beg, It end) -> typename remove_reference<decltype(*beg)>::type
{
    // 处理序列
    return *beg; // 返回序列中一个元素的拷贝
}
注意，type是一个类的成员，而该类依赖于一个模板参数。因此，我们必须在返回类型的声明中使用typename来告知编译器，type表示一个类型（参见16.1.3节，第593页）
    */

    // 16.2.4 函数指针和实参推断
    // 当我们用一个函数模板初始化一个函数指针或为一个函数指针赋值（参见6.7节，第221页）时，编译器使用指针的类型来推断模板实参。
    // 例如，假定我们有一个函数指针，它指向的函数返回int，接受两个参数，每个参数都是指向const int的引用。我们可以使用该指针指向compare的一个实例：
    /*
template<typename T> int compare(const T&, const T&);
// pf1指向实例int compare(cosnt int&, const int&)
int (*pf1) (const int&, const int&) = compare;
如果不能从函数指针类型确定模板实参，则产生错误：
// func的重载版本；每个版本接受一个不同的函数指针类型
void func(int (*) (const int&, const int&));
void func(int (*) (const string&, const string&));
func(compare); // 错误：使用compare的哪个实例？
我们可以通过使用显式模板实参来消除func调用的歧义：
// 正确：显示指出实例化哪个compare版本
func(compare<int>); // 正确：使用compare<int>的实例
    */
    // 当参数是一个函数模板实例的地址时，程序上下文必须满足：对每个模板参数，能唯一确定其类型或值。

    // 16.2.5 模板实参推断和引用
    // 为了理解如何从函数调用进行类型推断，考虑下面的例子：template<typename T> void f(T &p);
    // 其中函数参数p是一个模板类型参数T的引用，非常重要的是记住两点：编译器会应用正常的引用绑定规则；const是底层的，不是顶层的。

    // 从左值引用函数参数推断类型
    // 当一个函数参数是模板类型参数的一个普通（左值）引用时（即，形如T&），绑定规则告诉我们，只能传递给它一个左值（如，一个变量或一个返回引用类型的表达式）。实参可以是const类型，也可以不是。
    //   如果实参是const的，则T将被推断为const类型：
    /*
template<typename T> void f1(T &); // 实参必须是一个左值
f1(i);  // i是一个int；模板参数T是int
fi(ci); // ci是一个const int；模板参数T是const int
fi(5);  // 错误：传递给一个&参数的实参必须是一个左值
如果一个函数参数的类型是const T&，正常的绑定规则告诉我们可以传递给它任何类型的实参——一个对象（const或非const）、一个临时对象或是一个字面常量值。
  当函数参数本身是const时，T的类型推断的结果不会是一个const类型。const已经是函数参数类型的一部分；因此，它不会也是模板参数类型的一部分：
template<typename T> void f2(const T&); // 可以接受一个右值
f2(i);  // i是一个int；模板参数T是int
f2(ci); // ci是一个const int；但模板参数Tint
f2(5);  // 一个const &参数可以绑定到一个右值；T是int
    */

    // 从右值引用函数参数推断类型
    // 当一个函数参数是一个右值引用（参见13.6.1节，第471页）（即，形如T&&）时，正常绑定规则告诉我们可以传递给它一个右值。当我们这样做时，类型推断过程类似普通左值引用函数参数的推断过程。
    // template<typename T> void f3(T&&);
    // f3(42); // 实参是一个int类型的右值；模板参数T是int

    // 引用折叠和右值引用参数
    // 右值引用参数可以绑定到左值上，但是左值不能绑定到右值上
    /*
假定i是一个int对象，我们可能认为像f3（i）这样的调用是不合法的。毕竟，i是一个左值，而通常我们不能将一个右值引用绑定到一个左值上。但是，C++语言在正常绑定规则之外定义了两个例外规则，允许这种绑定。
  这两个例外规则是move这种标准库设施正确工作的基础。
第一个例外规则影响右值引用参数的推断如何进行。当我们将一个左值（如i）传递给函数的右值引用参数，且此右值引用指向模板类型参数（如T&&）时，编译器推断模板类型参数为实参的左值引用类型。
  因此，当我们调用f3（i）时，编译器推断T的类型为int&，而非int。
T被推断为int&看起来好像意味着f3的函数参数应该是一个类型int&的右值引用。通常，我们不能（直接）定义一个引用的引用（参见2.3.1节，第46页）。
  但是，通过类型别名（参见2.5.1节，第60页）或通过模板类型参数间接定义是可以的。
在这种情况下，我们可以使用第二个例外绑定规则：如果我们间接创建一个引用的引用，则这些引用形成了“折叠”。在所有情况下（除了一个例外），引用会折叠成一个普通的左值引用类型。
  在新标准中，折叠规则扩展到右值引用。只在一种特殊情况下引用会折叠成右值引用：右值引用的右值引用。即，对于一个给定类型X：· X&&、X&&&和X&&&都折叠成类型X&· 类型X&&&&折叠成X&&
    */
    // 引用折叠只能应用于间接创建的引用的引用，如类型别名或模板参数。
    /*
如果将引用折叠规则和右值引用的特殊类型推断规则组合在一起，则意味着我们可以对一个左值调用f3。当我们将一个左值传递给f3的（右值引用）函数参数时，编译器推断T为一个左值引用类型：
f3(i);  // 实参是一个左值；模板参数T是int&
f3(ci); // 实参是一个左值；模板参数T是const int&
f3(i)的函数参数是T&&且T是int&，因此T&&是int&&&，会折叠成int&。因此，即使f3的函数参数形式是一个右值引用（即，T&&），此调用也会用一个左值引用类型（即，int&）实例化f3：
    */
    // 如果一个函数参数是指向模板参数类型的右值引用（如，T&&），则可以传递给它任意类型的实参。如果将一个左值传递给这样的参数，则函数参数被实例化为一个普通的左值引用（T&）。

    // 编写接受右值引用参数的模板函数
    // 模板参数可以推断为一个引用类型，这一特性对模板内的代码可能有令人惊讶的影响：
    /*
template<typename T> void f3(T&& val)
{
    T t = val;  // 拷贝还是绑定一个引用？
    t = fcn(t); // 赋值是只改变t还是既改变t又改变val？
    if(val == t) {  } // 若T是引用类型，则一直为true
}   
当代码中涉及的类型可能是普通（非引用）类型，也可能是引用类型时，编写正确的代码就变得异常困难（虽然remove_reference这样的类型转换类可能会有帮助（参见16.2.3节，第605页））。
在实际中，右值引用通常用于两种情况：模板转发其实参或模板被重载。我们将在16.2.7节（第612页）中介绍实参转发，在16.3节（第614页）中介绍模板重载。
    */

    // 16.2.6 理解std::move
/*
标准库move函数（参见13.6.1节，第472页）是使用右值引用的模板的一个很好的例子。幸运的是，我们不必理解move所使用的模板机制也可以直接使用它。
  但是，研究move是如何工作的可以帮助我们巩固对模板的理解和使用。
在13.6.2节（第473页）中我们注意到，虽然不能直接将一个右值引用绑定到一个左值上，但可以用move获得一个绑定到左值上的右值引用。
  由于move本质上可以接受任何类型的实参，因此我们不会惊讶于它是一个函数模板。
*/
    
    // std：：move是如何定义的
/*
标准库是这样定义move的：
template<typename T>
typename remove_reference<T>::type&& move(T&& t)
{
    return static_cast<typename remove_reference<T>::type&&>(t);
}
这段代码很短，但其中有些微妙之处。首先，move的函数参数T&&是一个指向模板类型参数的右值引用。通过引用折叠，此参数可以与任何类型的实参匹配。
  特别是，我们既可以传递给move一个左值，也可以传递给它一个右值：
string s1("hi!"), s2;
s2 = std::move(string("bye!")); // 正确：从一个右值移动数据
s2 = std::move(s1);             // 正确：但在赋值后，s1的值是不确定的
*/

    // std：：move是如何工作的
    /*
现在考虑第二个赋值，它调用了std：：move（）。在此调用中，传递给move的实参是一个左值。这样：
  · 推断出的T的类型为string&（string的引用，而非普通string）。
  · 因此，remove_reference用string&进行实例化。
  · remove_reference<string&>的type成员是string。
  · move的返回类型仍是string&&。
  · move的函数参数t实例化为string&&&，会折叠为string&。因此，这个调用实例化move<string&>，即:string&& move(string &t)
这正是我们所寻求的——我们希望将一个右值引用绑定到一个左值。这个实例的函数体返回static_cast<string&&>（t）。在此情况下，t的类型为string&，cast将其转换为string&&。
    */

    // 从一个左值static_cast到一个右值引用是允许的
    /*
通常情况下，static_cast只能用于其他合法的类型转换（参见4.11.3节，第145页）。但是，这里又有一条针对右值引用的特许规则：
  虽然不能隐式地将一个左值转换为右值引用，但我们可以用static_cast显式地将一个左值转换为一个右值引用。
    */

    // 16.2.7 转发
    // 某些函数需要将其一个或多个实参连同类型不变地转发给其他函数。在此情况下，我们需要保持被转发实参的所有性质，包括实参类型是否是const的以及实参是左值还是右值。
    /*
作为一个例子，我们将编写一个函数，它接受一个可调用表达式和两个额外实参。我们的函数将调用给定的可调用对象，将两个额外参数逆序传递给它。下面是我们的翻转函数的初步模样：
// flip1是一个不完整的实现：顶层const和引用丢失了
template <typename F, typename T1, typename T2>
void flip1(F f, T1 t1, T2 t2)
{
    f(t2, t1);
}
这个函数一般情况下工作得很好，但当我们希望用它调用一个接受引用参数的函数时就会出现问题：
void f(int v1, int &v2) // 注意v2是个引用
{
    cout << v1 << " " << ++v2 << endl;
}
在这段代码中，f改变了绑定到v2的实参的值。但是，如果我们通过flip1调用f，f所做的改变就不会影响实参：
f(42, i);        // f改变了实参i
flip1(f, j, 42); // 通过flip1调用f不会改变j
问题在于j被传递给flip1的参数t1。此参数是一个普通的、非引用的类型int，而非int&。因此，这个flip1调用会实例化为
void flip1(void (*fun)(int, int&), int, int);
j的值被拷贝到t1中。f中的引用参数被绑定到t1，而非j，从而其改变不会影响j。
    */
    
    // 定义能保持类型信息的函数参数
    /*
通过将一个函数参数定义为一个指向模板类型参数的右值引用，我们可以保持其对应实参的所有类型信息。而使用引用参数（无论是左值还是右值）使得我们可以保持const属性，因为在引用类型中的const是底层的。
如果我们将函数参数定义为T1&&和T2&&，通过引用折叠（参见16.2.5节，第608页）就可以保持翻转实参的左值/右值属性（参见16.2.5节，第608页）：
template<typename F, typename T1, typename T2>
void flip2(F f, T1&& t1, T2&& t2)
{
    f(t2, t1);
}
与较早的版本一样，如果我们调用flip2（f，j，42），将传递给参数t1一个左值j。但是，在flip2中，推断出的T1的类型为int&，这意味着t1的类型会折叠为int&。
  由于是引用类型，t1被绑定到j上。当flip2调用f时，f中的引用参数v2被绑定到t1，也就是被绑定到j。当f递增v2时，它也同时改变了j的值。
    */
    // 如果一个函数参数是指向模板类型参数的右值引用（如T&&），它对应的实参的const属性和左值/右值属性将得到保持。
    /*
这个版本的flip2解决了一半问题。它对于接受一个左值引用的函数工作得很好，但不能用于接受右值引用参数的函数。例如：
void g(int &&i, int & j)
{
    cout << i << " " << j << endl;
}
如果我们试图通过flip2调用g，则参数t2将被传递给g的右值引用参数。即使我们传递一个右值给flip2：
flip2(g, i, 42); // 错误：
传递给g的将是flip2中名为t2的参数。函数参数与其他任何变量一样，都是左值表达式（参见13.6.1节，第471页）。因此，flip2中对g的调用将传递给g的右值引用参数一个左值。
    */

    // 在调用中使用std：：forward保持类型信息
    /*
我们可以使用一个名为forward的新标准库设施来传递flip2的参数，它能保持原始实参的类型。类似move，forward定义在头文件utility中。
  与move不同，forward必须通过显式模板实参来调用（参见16.2.2节，第603页）。forward返回该显式实参类型的右值引用。即，forward<T>的返回类型是T&&。
通常情况下，我们使用forward传递那些定义为模板类型参数的右值引用的函数参数。通过其返回类型上的引用折叠，forward可以保持给定实参的左值/右值属性：
template<typename Type> intermediary(Type &&arg)
{
    finalFcn(std::forward<Type>(arg))
}
当用于一个指向模板参数类型的右值引用函数参数（T&&）时，forward会保持实参类型的所有细节。
与std：：move相同，对std：：forward不使用using声明是一个好主意。我们将在18.2.3节（第706页）中解释原因。
    */

    return 0;
}